/LMAR=0/XLINE=3/FONT#0=FIX25



␈↓ ↓H␈↓;vsp 25
␈↓ ↓H␈↓;skip 1
␈↓ ↓H␈↓;topmar 250
␈↓ ↓H␈↓;lftmar 250
␈↓ ↓H␈↓;botmar 250
␈↓ ↓H␈↓                    LISP - AN AMICUS CURIAE BRIEF
␈↓ ↓H␈↓                            V. R. Pratt
␈↓ ↓H␈↓                              1/10/77
␈↓ ↓H␈↓                                                -- To the complexity of
␈↓ ↓H␈↓                                                building a single interfa
␈↓ ↓H␈↓                                                between people, machines,
␈↓ ↓H␈↓                                                and problems, which has
␈↓ ↓H␈↓                                                made this brief so long.
␈↓ ↓H␈↓        This position paper advances reasons in support of the
␈↓ ↓H␈↓consideration of LISP as the language of choice for use within the
␈↓ ↓H␈↓M.I.T. Electrical Engineering and Computer Science Department. There
␈↓ ↓H␈↓being no universally agreed on dialect of LISP to date, I have chosen
␈↓ ↓H␈↓to describe MACLISP, the dialect implemented at MIT. Even with such a
␈↓ ↓H␈↓concrete object as an implementation there is room for interpretation
␈↓ ↓H␈↓of what has been implemented. Thus it must be realized that the
␈↓ ↓H␈↓following represents one individual's perspective on one dialect of
␈↓ ↓H␈↓LISP.
␈↓ ↓H␈↓        The paper is divided into three sections. The first two
␈↓ ↓H␈↓consider LISP ␈↓&in␈↓)αβ ␈↓&vacuo␈↓)αβ, without detailed reference to other languages
␈↓ ↓H␈↓and without considering departmental needs. The third section takes
␈↓ ↓H␈↓into account what we need a programming language for.
␈↓ ↓H␈↓A. Merits of LISP.
␈↓ ↓H␈↓        There are ten sections below, with first sentences as follows.
␈↓ ↓H␈↓1. LISP is versatile.
␈↓ ↓H␈↓2. LISP is efficient.
␈↓ ↓H␈↓3. LISP uses a standard character set.
␈↓ ↓H␈↓4. LISP is interactive.
␈↓ ↓H␈↓5. LISP is modular.
␈↓ ↓H␈↓6. LISP is notation-independent.
␈↓ ↓H␈↓7. LISP is applicative.
␈↓ ↓H␈↓8. LISP is widely used in academia.
␈↓ ↓H␈↓9. LISP is used by half the MIT Computer Science faculty.
␈↓ ↓H␈↓10. No other language enjoys all the above advantages of LISP.
␈↓ ↓H␈↓ 
␈↓ ↓H␈↓1. LISP is versatile. Although LISP is caricatured by non-LISP
␈↓ ↓H␈↓users as being of use mainly for manipulation of irregularly
␈↓ ↓H␈↓structured data, this caricature does little justice to the careful
␈↓ ↓H␈↓work done by McCarthy, Levin and others in the formative years of LISP
␈↓ ↓H␈↓(around 1960) in developing a mathematically clean yet general
␈↓ ↓H␈↓programming language. Certainly Artificial Intelligence applications
␈↓ ↓H␈↓were a concern during that development; after all, AI was the nutrient
␈↓ ↓H␈↓medium within which LISP developed. Yet the language has managed to
␈↓ ↓H␈↓remain remarkably free of the concessions one might expect to arise
␈↓ ↓H␈↓from such pressures, and is in our view one of the most



␈↓ ↓H␈↓domain-independent languages currently enjoying wide usage.
␈↓ ↓H␈↓        We may illustrate LISP's versatility by reference to its data
␈↓ ↓H␈↓types. These are:
␈↓ ↓H␈↓        numbers integers (unlimited size), reals
␈↓ ↓H␈↓        bit vectors various applications, e.g. PASCAL's sets
␈↓ ↓H␈↓        booleans T and NIL (for false)
␈↓ ↓H␈↓        atoms serving double duty as strings and variables
␈↓ ↓H␈↓        lists for which LISP is best known
␈↓ ↓H␈↓        property lists various applications, e.g. PASCAL's records
␈↓ ↓H␈↓        arrays unrestricted as to type or dimension
␈↓ ↓H␈↓        function(al)s using LAMBDA and APPLY
␈↓ ↓H␈↓        programs using EVAL and QUOTE
␈↓ ↓H␈↓        In the MACLISP implementation the above data types are almost
␈↓ ↓H␈↓"first-class citizens," a term used by the implementors of POP-2 [5]
␈↓ ↓H␈↓to describe a data type that can be passed as a parameter, returned by
␈↓ ↓H␈↓a function as a value, assigned to a variable, and tested for
␈↓ ↓H␈↓equality. LISP's data types include some for which equality cannot be
␈↓ ↓H␈↓decided, namely the last two. If we rule out the last requirement,
␈↓ ↓H␈↓then all LISP data types are first-class citizens.
␈↓ ↓H␈↓        It is hard to appreciate what first-class citizenship really
␈↓ ↓H␈↓means until one has programmed with and without it. Now that I have
␈↓ ↓H␈↓adopted a programming style which capitalizes on this asset of LISP, I
␈↓ ↓H␈↓find that I have been able to clean up my programming style to the
␈↓ ↓H␈↓point where I feel I am saying things the right way. This is no more
␈↓ ↓H␈↓than a generalization to other data types of the experience of a
␈↓ ↓H␈↓generation of LISP programmers in writing programs that treat numbers
␈↓ ↓H␈↓and lists as first-class citizens. MACLISP has merely extended this
␈↓ ↓H␈↓convenience to its other data types. For me to return to the situation
␈↓ ↓H␈↓that obtains in, say, ALGOL or PASCAL, where an array-producing
␈↓ ↓H␈↓subroutine must be given the array as input, would force me back to a
␈↓ ↓H␈↓clumsy style that I now know is unnecessary. The same remark applies
␈↓ ↓H␈↓to the other data types; for example the ability to pass property
␈↓ ↓H␈↓lists around without requiring that they be attached to a particular
␈↓ ↓H␈↓atom made it possible for me to implement the Boyer-Moore unification
␈↓ ↓H␈↓algorithm in a cleaner way than Boyer and Moore implemented it.
␈↓ ↓H␈↓        For some, the data types FUNCTION and PROGRAM truly set LISP
␈↓ ↓H␈↓apart from other languages. To be precise, this power depends on
␈↓ ↓H␈↓objects of these types being first-class citizens in the POP-2 sense.
␈↓ ↓H␈↓This has certainly been the case for me. For a number of years,
␈↓ ↓H␈↓starting with the 1970 implementations of my LINGOL natural language
␈↓ ↓H␈↓system and my CGOL syntactic front-end for LISP, I have built much of
␈↓ ↓H␈↓my software around a central philosophy that is best described as
␈↓ ↓H␈↓ACTOR-oriented [2]. I store information in small modules that can be
␈↓ ↓H␈↓evaluated by LISP when they need to be queried. The advantage of this
␈↓ ↓H␈↓style is that such information can be made context-dependent because
␈↓ ↓H␈↓like all LISP code it has access to the environment. Moreover a
␈↓ ↓H␈↓module can be "intelligent" about what it answers, possibly calling on
␈↓ ↓H␈↓other modules for help before making up its mind. Good examples of
␈↓ ↓H␈↓how powerful this technique can be in practical situations can be



␈↓ ↓H␈↓found in [7] and [8]. Carl Hewitt has built a whole programming
␈↓ ↓H␈↓language based solely on this philosophy (which arose in his case out
␈↓ ↓H␈↓of his earlier work on PLANNER) and has demonstrated how ACTORS can by
␈↓ ↓H␈↓themselves supply the only foundations needed for a versatile and
␈↓ ↓H␈↓efficient programming language, using methods analogous to the
␈↓ ↓H␈↓corresponding demonstration for the pure lambda-calculus.
␈↓ ↓H␈↓2. LISP is efficient. Another myth popular among non-LISP users
␈↓ ↓H␈↓is that to use LISP one resigns oneself to gross inefficiency.
␈↓ ↓H␈↓To put this shibboleth to the test, members of the MACSYMA project
␈↓ ↓H␈↓took some numerical benchmark programs of the sort that one would
␈↓ ↓H␈↓normally think of as being well-suited to FORTRAN compilation, and
␈↓ ↓H␈↓compared their running times under each of an (admittedly old) FORTRAN
␈↓ ↓H␈↓compiler and the LISP compiler used at MIT on ITS [1]. Both
␈↓ ↓H␈↓compilations were performed on the same machine, a PDP-10. The LISP
␈↓ ↓H␈↓compiler won! With a little thought it becomes apparent that
␈↓ ↓H␈↓inefficient object code does not inhere in a language but rather is
␈↓ ↓H␈↓the result either of the program demanding something difficult such as
␈↓ ↓H␈↓a complicated parameter-passing task, or of the compiler-writers not
␈↓ ↓H␈↓doing a good job. After all, why should the FORTRAN statement
␈↓ ↓H␈↓      A(I,J) = B(I,K)*C(K,J)
␈↓ ↓H␈↓and the LISP statement
␈↓ ↓H␈↓      (STORE (A I J) (TIMES (B I K) (C K J)))
␈↓ ↓H␈↓produce different object code? In fact, in the experiment cited
␈↓ ↓H␈↓above, the slight superiority of the LISP code (involving an
␈↓ ↓H␈↓insignificant factor of about 1.2) was traceable not to the code
␈↓ ↓H␈↓generated for the arithmetic parts of the program, which was almost
␈↓ ↓H␈↓identical in each case, but rather to the more efficient procedure
␈↓ ↓H␈↓calling in LISP. This I feel convincingly disposes of the argument
␈↓ ↓H␈↓that FORTRAN (and hence presumably most other high level languages) is
␈↓ ↓H␈↓more appropriate when efficiency is needed.
␈↓ ↓H␈↓        Professor Bers group, which although in EECS is not a part of
␈↓ ↓H␈↓the Computer Science laboratories (LCS and AI), does considerable
␈↓ ↓H␈↓"number crunching," having used several hundred hours of computer time
␈↓ ↓H␈↓for a variety of heavily numerical problems. John L. Kulp of that
␈↓ ↓H␈↓group has experimented with a few numerical problems using FORTRAN on
␈↓ ↓H␈↓MULTICS and the 370/168, and LISP (under MACSYMA) on a PDP10 with a
␈↓ ↓H␈↓KL-10 processor. Although the arithmetic unit on the 168 has twice
␈↓ ↓H␈↓the speed of that on the KL-10, that group has chosen to do most of
␈↓ ↓H␈↓their work on the PDP-10 in LISP/MACSYMA, both because that factor of
␈↓ ↓H␈↓two is considerably diluted by the associated and inevitable
␈↓ ↓H␈↓non-numeric processing and because of the advantages of LISP over
␈↓ ↓H␈↓FORTRAN. (It should be noted that MACSYMA uses an algebraic notation,
␈↓ ↓H␈↓removing any notational advantage FORTRAN may possess over the
␈↓ ↓H␈↓standard LISP notation.)
␈↓ ↓H␈↓        This is not to say that one cannot write LISP programs that
␈↓ ↓H␈↓are inefficient. In a language as versatile as LISP it is inevitable
␈↓ ↓H␈↓that the user will want to take advantage of constructs that
␈↓ ↓H␈↓linguistically express perfectly what he is trying to say but
␈↓ ↓H␈↓computationally present obstacles to efficient code generation. Our



␈↓ ↓H␈↓position on this is that the default should be that the programmer
␈↓ ↓H␈↓feel no compunctions about using to the full the features of a
␈↓ ↓H␈↓language, but that on those occasions when it truly is the case that
␈↓ ↓H␈↓the machine's time is worth more than the programmer's (together with
␈↓ ↓H␈↓the time of those who have to read his code) then the programmer
␈↓ ↓H␈↓should know which constructions to avoid to permit the optimizer to do
␈↓ ↓H␈↓as good a job with his code as a good FORTRAN optimizer can do. Thus
␈↓ ↓H␈↓a systems programmer writing widely used systems code in LISP might as
␈↓ ↓H␈↓a general policy avoid heavy use of functions that do considerable
␈↓ ↓H␈↓work to keep the environment in a consistent state such as code
␈↓ ↓H␈↓associated with LISP's "special" variables. (If one doubts that
␈↓ ↓H␈↓efficient systems programming can be done in LISP, I should point to
␈↓ ↓H␈↓the CGOL subsystem of LISP that I have developed to provide an
␈↓ ↓H␈↓algebraic notation for MACLISP users, discussed in more detail in
␈↓ ↓H␈↓section 6. Users of this dialect sacrifice approximately a factor of
␈↓ ↓H␈↓two in speed in reading their programs into LISP when they are running
␈↓ ↓H␈↓those programs interpretively, and a negligible amount when they are
␈↓ ↓H␈↓compiling their programs. Some of this can be attributed to the
␈↓ ↓H␈↓greater complexity of parsing an algebraic as opposed to a fully
␈↓ ↓H␈↓parenthesized prefix notation, and the remainder to the fact that the
␈↓ ↓H␈↓subsystem is written in LISP instead of assembly language. I believe
␈↓ ↓H␈↓a substantial proportion of this gap can be eliminated by writing the
␈↓ ↓H␈↓LISP code with more attention to speed; at present it is written with
␈↓ ↓H␈↓concern only for legibility and my programming time, with heavy use of
␈↓ ↓H␈↓the fore-mentioned "special" variables and "over-modularization" of
␈↓ ↓H␈↓the code resulting in many more procedure calls than really
␈↓ ↓H␈↓necessary.)
␈↓ ↓H␈↓3. LISP uses a standard character set. Essentially all
␈↓ ↓H␈↓general-purpose terminals on the market today adhere pretty closely to
␈↓ ↓H␈↓the ASCII standard character set. It would be next to unthinkable for
␈↓ ↓H␈↓a language designer today to propose a language that made heavy use of
␈↓ ↓H␈↓a radically different character set, so this claim almost goes without
␈↓ ↓H␈↓saying.
␈↓ ↓H␈↓4. LISP is interactive. If one wants to know the value of 1+1
␈↓ ↓H␈↓while "talking to" LISP, one types (PLUS 1 1) and LISP replies 2
␈↓ ↓H␈↓without further ado. If one wants to get a big job underway, one
␈↓ ↓H␈↓simply invokes the top-level function of that job in exactly the same
␈↓ ↓H␈↓way. And of course one's program can always type directly to the user
␈↓ ↓H␈↓and accept input from him at any time. Perhaps more significantly,
␈↓ ↓H␈↓one can interact with one's program while it is running, interrupting
␈↓ ↓H␈↓to both modify and/or examine the environment. In powerful languages
␈↓ ↓H␈↓like LISP, environment examination is made more complicated by the
␈↓ ↓H␈↓complexity of the environment; nevertheless LISP provides the tools
␈↓ ↓H␈↓needed to explore nested contexts and complex data structures.
␈↓ ↓H␈↓5. LISP is modular. One of the joys of programming in LISP is
␈↓ ↓H␈↓that almost everything one does can be done incrementally, either on
␈↓ ↓H␈↓the user's command or under program control in all cases. If one is
␈↓ ↓H␈↓running a LISP program and wants to interrupt it to write another
␈↓ ↓H␈↓function, one can do so on the spot without having to re-read the



␈↓ ↓H␈↓whole program back into LISP. If one takes a dislike to the behavior
␈↓ ↓H␈↓of the lexical analyzer, its behavior can be modified on the spot,
␈↓ ↓H␈↓either locally or by wholesale and instantaneous replacement with a
␈↓ ↓H␈↓new analyzer. If the routine used by the top-level listen loop to
␈↓ ↓H␈↓print the answer is inappropriate to the task, it can be changed in
␈↓ ↓H␈↓one command; in fact, the entire top-level listen loop can be
␈↓ ↓H␈↓replaced. If a given system-defined function such as PLUS is not to
␈↓ ↓H␈↓the user's taste he can simply supply his own, without having to
␈↓ ↓H␈↓change every occurrence of PLUS in his program to a user-defined
␈↓ ↓H␈↓name. Even the READ function invoked by the top-level listen loop can
␈↓ ↓H␈↓be replaced with a user supplied function, an advantage so important
␈↓ ↓H␈↓that we afford it special treatment in the next section.
␈↓ ↓H␈↓        LISP's modularity is important not only to a single programmer
␈↓ ↓H␈↓but to groups of programmers cooperating on a project. When one
␈↓ ↓H␈↓develops a LISP program for a specific application, it can be used
␈↓ ↓H␈↓later as a subroutine of somebody else's program. While this is true
␈↓ ↓H␈↓to a limited extent of most languages, it holds to a much greater
␈↓ ↓H␈↓extent in LISP. When I developed a natural language system several
␈↓ ↓H␈↓years ago I had in mind that I would be using it as a stand-alone
␈↓ ↓H␈↓system. However it has found use in the AI lab and in LCS as a
␈↓ ↓H␈↓subroutine that other programs can call to get the translation of the
␈↓ ↓H␈↓English being typed by the program's user. In the middle of preparing
␈↓ ↓H␈↓this document a Harvard graduate student working with the MACSYMA
␈↓ ↓H␈↓project, Michael Genesereth, came into my office to ask me whether he
␈↓ ↓H␈↓could attach my natural language front end to his MACSYMA
␈↓ ↓H␈↓advice-giving program. The task proved trivial; after a bit of
␈↓ ↓H␈↓ferreting around in my files and a quick demonstration I gave him the
␈↓ ↓H␈↓file and the name of the subroutine to call. He went away, and ten
␈↓ ↓H␈↓minutes later sent me a message on the computer expressing delight
␈↓ ↓H␈↓that it was doing just what he needed.
␈↓ ↓H␈↓        Another example of this modularity concerns a
␈↓ ↓H␈↓program-proof-checker that Steve Litvintchouk, a graduate student of
␈↓ ↓H␈↓mine, has been writing in LISP. He complained to me that entering
␈↓ ↓H␈↓statements about programs into the computer was painfully slow because
␈↓ ↓H␈↓he was using standard LISP notation. So I made up a formal definition
␈↓ ↓H␈↓of the notation we had been using in class, implemented it one
␈↓ ↓H␈↓afternoon, loaded it into a LISP that already had Litvintchouk's
␈↓ ↓H␈↓program loaded (after a few debugging runs of course) and we were then
␈↓ ↓H␈↓able to talk to his program in the notation we wanted. (Sample:
␈↓ ↓H␈↓[Y:=X+5]<Y:=Y-1*>X=Y asserts that after setting Y to X+5, it is
␈↓ ↓H␈↓possible by iterating Y:=Y-1 to reach a state in which X=Y. We were
␈↓ ↓H␈↓tiring of writing (([] (:= Y (+ X 5))) ((<> (* (:= Y (- Y 1)))) (= X Y)))
␈↓ ↓H␈↓to express the same thing.) The remarkable thing about this
␈↓ ↓H␈↓particular exercise is that I had no idea what his code looked like at
␈↓ ↓H␈↓the time as I had not then gotten around to reading it, and he had no
␈↓ ↓H␈↓idea how one went about changing notation in LISP. Yet despite this
␈↓ ↓H␈↓mutual ignorance, and without making ANY changes to his code, we were
␈↓ ↓H␈↓able to accomplish in a quite simple way what would require major
␈↓ ↓H␈↓surgery to the given program in almost any other language.



␈↓ ↓H␈↓6. LISP is notation-independent. Mathematically speaking, LISP
␈↓ ↓H␈↓programs form a set containing "atoms" and closed under the pairing
␈↓ ↓H␈↓function CONS. How such programs are to be represented is an
␈↓ ↓H␈↓implementation-dependent issue. In any implementation there are at
␈↓ ↓H␈↓least two representations, internal (consisting in the interpreted
␈↓ ↓H␈↓case of a graph whose nodes are computer words and whose edges are
␈↓ ↓H␈↓pointers, and in the compiled case of a string of machine
␈↓ ↓H␈↓instructions) and external (consisting traditionally of fully
␈↓ ↓H␈↓parenthesized prefix (forward Polish notation) expressions). However,
␈↓ ↓H␈↓this does not exhaust the possible representations of LISP programs by
␈↓ ↓H␈↓any means, a point that is frequently over-looked and yet one that was
␈↓ ↓H␈↓made right at the outset by McCarthy, who used what he called MLISP
␈↓ ↓H␈↓notation, an algebraic notation that PL/I users would feel much more
␈↓ ↓H␈↓comfortable with than the fully parenthesized prefix notation. An
␈↓ ↓H␈↓implementation of MLISP exists at Stanford, and is the notation of
␈↓ ↓H␈↓choice for LISP users there. At MIT an MLISP-like notation called
␈↓ ↓H␈↓CGOL is available to the LISP user: at any time, even half-way through
␈↓ ↓H␈↓running his program, he can simply say (CGOL) and from then on he can
␈↓ ↓H␈↓rephrase (QUOTIENT (PLUS (MINUS B) (SQRT (DIFFERENCE (EXPT B 2)
␈↓ ↓H␈↓                                            (TIMES 4 A C))))
␈↓ ↓H␈↓          (TIMES 2 A))
␈↓ ↓H␈↓as
␈↓ ↓H␈↓(-b+sqrt(b**2-4*a*c))/(2*a)
␈↓ ↓H␈↓or
␈↓ ↓H␈↓(MAPCAR '(LAMBDA (I J) (PRINT (CAT '|Buy | I '| for | J '| dollars.|)))
␈↓ ↓H␈↓        SHOPPINGLIST
␈↓ ↓H␈↓        PRICELIST)
␈↓ ↓H␈↓as
␈↓ ↓H␈↓for i in shoppinglist, j in pricelist do
␈↓ ↓H␈↓  print "Buy " ↑ i ↑ " for " ↑ j ↑ " dollars."
␈↓ ↓H␈↓and so on. The versatility of LISP in comparison to most other
␈↓ ↓H␈↓programming languages becomes more apparent in this notation because a
␈↓ ↓H␈↓more direct comparison is possible without the distraction of having
␈↓ ↓H␈↓to allow for radically different styles of notation. (An aside:
␈↓ ↓H␈↓although all programming languages deserving of the name can express
␈↓ ↓H␈↓the first of the above examples, very few can cope with the second
␈↓ ↓H␈↓quite so directly.)
␈↓ ↓H␈↓        The CGOL notation inherits LISP's modularity, in that it can
␈↓ ↓H␈↓be extended painlessly by the user even while in the middle of running
␈↓ ↓H␈↓a program. This legacy of LISP's puts this algebraic notation ahead
␈↓ ↓H␈↓of almost all other available algebraic programming languages with
␈↓ ↓H␈↓respect to syntactic extensibility. Only a few research systems come
␈↓ ↓H␈↓close to this level of convenience, such as Bell Laboratories'
␈↓ ↓H␈↓recently developed YACC (Yet Another Compiler-Compiler) system, a
␈↓ ↓H␈↓version of which has been developed by Alan Snyder at MIT and is used
␈↓ ↓H␈↓as the "front-end" of Barbara Liskov's CLU language at MIT. Even
␈↓ ↓H␈↓these advanced systems do not offer fast incremental extensibility of
␈↓ ↓H␈↓this syntactic front-end to LISP [6,8].
␈↓ ↓H␈↓        It may be instructive to compare an ALGOL program taken



␈↓ ↓H␈↓verbatim from the Communications of the Association for Computing
␈↓ ↓H␈↓Machinery, Algorithm 482 [3], with its rendering in this algebraic
␈↓ ↓H␈↓dialect of LISP. We give the ALGOL version first, changing only its
␈↓ ↓H␈↓comment section for the sake of brevity.
␈↓ ↓H␈↓comment We are given a set of towns numbered 1 to n. There are k one-way
␈↓ ↓H␈↓roads leading out of each town in such a way that if you ever go on a
␈↓ ↓H␈↓trip you can always get back home again, though not necessarily by
␈↓ ↓H␈↓retracing your steps. However, it is not guaranteed that you can
␈↓ ↓H␈↓always get to the town of your choice. The problem is to group the
␈↓ ↓H␈↓towns into equivalence classes of mutually accessible towns.
␈↓ ↓H␈↓        The roads are represented by an array im[1:n, 1:k] such that
␈↓ ↓H␈↓im[r,q] is the q-th town accessible from town r. You are given two
␈↓ ↓H␈↓arrays ind[1:n] and orb[1:n] to store the results in. Town i is to be
␈↓ ↓H␈↓in the ind[i]-th equivalence class. Orb[i] is a list of towns
␈↓ ↓H␈↓arranged so that each equivalence class is in a contiguous block; the
␈↓ ↓H␈↓first town of each block is stored with its sign bit complemented (in
␈↓ ↓H␈↓particular town 1 will appear in orb[1] as -1) to distinguish the
␈↓ ↓H␈↓beginning of the block.
␈↓ ↓H␈↓        (The problem was stated in CACM in group-theoretic terms, with
␈↓ ↓H␈↓orb referring to orbits of group elements, but the ALGOL solution
␈↓ ↓H␈↓given in CACM solves the more general problem we have just described.)
␈↓ ↓H␈↓procedure orbits(ind, orb, im, n, k);
␈↓ ↓H␈↓  value n, k; ␈↓&integer␈↓)αβ n, k;
␈↓ ↓H␈↓  integer ␈↓&array␈↓)αβ ind, orb, im;
␈↓ ↓H␈↓begin
␈↓ ↓H␈↓  integer q, r, s, j, nt, ns, norb;
␈↓ ↓H␈↓  for j := 1 ␈↓&step␈↓)αβ 1 ␈↓&until␈↓)αβ n ␈↓&do␈↓)αβ ind[j] := 0;
␈↓ ↓H␈↓  norb := 0; ns := 1;
␈↓ ↓H␈↓  for r := 1 ␈↓&step␈↓)αβ 1 ␈↓&until␈↓)αβ n ␈↓&do␈↓)αβ ␈↓&if␈↓)αβ ind[r] = 0 ␈↓&then␈↓)αβ
␈↓ ↓H␈↓  begin
␈↓ ↓H␈↓    norb := norb + 1; ind[r] := norb;
␈↓ ↓H␈↓    nt := ns; orb[ns] := -r; s := r;
␈↓ ↓H␈↓a:
␈↓ ↓H␈↓    ns := ns + 1;
␈↓ ↓H␈↓    for j := 1 ␈↓&step␈↓)αβ 1 ␈↓&until␈↓)αβ k ␈↓&do␈↓)αβ
␈↓ ↓H␈↓    begin
␈↓ ↓H␈↓      q := im[s,j];
␈↓ ↓H␈↓      if ind[q] = 0 ␈↓&then␈↓)αβ
␈↓ ↓H␈↓      begin
␈↓ ↓H␈↓        nt := nt + 1; orb[nt] := q; ind[q] := norb
␈↓ ↓H␈↓      end
␈↓ ↓H␈↓    end;
␈↓ ↓H␈↓    if ns
␈↓ ↓H␈↓    begin s := orb[ns]; ␈↓&go␈↓)αβ ␈↓&to␈↓)αβ a ␈↓&end␈↓)αβ
␈↓ ↓H␈↓  end
␈↓ ↓H␈↓end
␈↓ ↓H␈↓        The following is the LISP rendering of the above procedure,
␈↓ ↓H␈↓using the algebraic dialect. For direct comparison we have adhered as
␈↓ ↓H␈↓closely as possible to the layout of the above program.



␈↓ ↓H␈↓define "ORBITS"(ind, orb, im, n, k);
␈↓ ↓H␈↓(
␈↓ ↓H␈↓  new q, r, s, j, nt, ns, norb;
␈↓ ↓H␈↓  for j in 1 to n do ind(j) := 0;
␈↓ ↓H␈↓  norb := 0; ns := 1;
␈↓ ↓H␈↓  for r in 1 to n do if ind(r) = 0 then
␈↓ ↓H␈↓  (prog; % necessitated by the presence of (ugh) goto %
␈↓ ↓H␈↓    norb := norb + 1; ind(r) := norb;
␈↓ ↓H␈↓    nt := ns; orb(ns) := -r; s := r;
␈↓ ↓H␈↓a;
␈↓ ↓H␈↓    ns := ns + 1;
␈↓ ↓H␈↓    for j in 1 to k do
␈↓ ↓H␈↓    (
␈↓ ↓H␈↓      q := im(s,j);
␈↓ ↓H␈↓      if ind(q) = 0 then
␈↓ ↓H␈↓      (
␈↓ ↓H␈↓        nt := nt + 1; orb(nt) := q; ind(q) := norb
␈↓ ↓H␈↓      )
␈↓ ↓H␈↓    );
␈↓ ↓H␈↓    if ns <= nt then
␈↓ ↓H␈↓    ( s := orb(ns); go a )
␈↓ ↓H␈↓  )
␈↓ ↓H␈↓)
␈↓ ↓H␈↓        The only differences in this example are:
␈↓ ↓H␈↓ALGOL LISP
␈↓ ↓H␈↓a[b] a(b) (arrays)
␈↓ ↓H␈↓begin ␈↓&end␈↓)αβ ( ) (block delimiters)
␈↓ ↓H␈↓integer new (type declarations inessential)
␈↓ ↓H␈↓procedure (and related text) define (and related text)
␈↓ ↓H␈↓for i := 1 ␈↓&step␈↓)αβ 1 ␈↓&until␈↓)αβ n for i in 1 to n
␈↓ ↓H␈↓a: (and associated ␈↓&goto␈↓)αβ) a; (and associated prog and go)
␈↓ ↓H␈↓value redundant (arrays may be values in LISP)
␈↓ ↓H␈↓-1
␈↓ ↓H␈↓        Except for ␈↓&value␈↓)αβ and LISP and the second of which is not availabl
␈↓ ↓H␈↓character set, none of these differences are essential; the CGOL
␈↓ ↓H␈↓notation, being user extensible, can be modified either by the
␈↓ ↓H␈↓individual user, or by the system programmers when a sufficiently
␈↓ ↓H␈↓large demand exists, to permit the use of the first seven of the above
␈↓ ↓H␈↓ALGOL constructs, at least for this example (where we were fortunate
␈↓ ↓H␈↓that we could translate ALGOL's ␈↓&goto␈↓)αβ directly; ␈↓&goto␈↓)αβ's out of blocks
␈↓ ↓H␈↓require a more involved translation into LISP in general, as does call
␈↓ ↓H␈↓by name.) However I do not foresee frequent use being made of such
␈↓ ↓H␈↓modifications to the notation.
␈↓ ↓H␈↓        The above comparison is a little like having a race between a
␈↓ ↓H␈↓Ford and a Porsche where the drivers are required to behave
␈↓ ↓H␈↓identically. After a few seconds the Porsche driver starts to grumble
␈↓ ↓H␈↓about being in third gear when he should be in fifth. In the above
␈↓ ↓H␈↓example there is some clumsy programming going on that is the result
␈↓ ↓H␈↓of programming in a language that does not provide adequately for



␈↓ ↓H␈↓irregularly structured data. Actually, the input of this example (the
␈↓ ↓H␈↓array im) is regularly structured, but the result (the array orb)
␈↓ ↓H␈↓attempts clumsily (using the sign bits of its entries) to represent
␈↓ ↓H␈↓the irregularly structured answer.
␈↓ ↓H␈↓        We give below another version of the same algorithm, this time
␈↓ ↓H␈↓relaxing the constraint that we have to mimic the ALGOL solution as
␈↓ ↓H␈↓closely as possible. First we observe that the array im is really the
␈↓ ↓H␈↓only input data required. Second, we suggest that im be represented
␈↓ ↓H␈↓as a vector of lists, allowing a variable number of roads to leave
␈↓ ↓H␈↓each town. (In the group-theoretic special case of this problem, k is
␈↓ ↓H␈↓fixed, corresponding to having k generators of an n element group, but
␈↓ ↓H␈↓the solution given in CACM makes no essential use of k being fixed.)
␈↓ ↓H␈↓Third, we suggest that the answer be an array (corresponding to ind in
␈↓ ↓H␈↓the above program) whose i-th element is the list of towns accessible
␈↓ ↓H␈↓from town i (numbering these equivalence lists as in the above
␈↓ ↓H␈↓programs seems pointless).
␈↓ ↓H␈↓        All variables except adi (array dimensions of im) correspond
␈↓ ↓H␈↓to variables used in the above programs, though they may not be of the
␈↓ ↓H␈↓same type.
␈↓ ↓H␈↓define "ORBITS" im;
␈↓ ↓H␈↓let adi = arraydims im;
␈↓ ↓H␈↓let ind = array{nil . adi}, n = cadr adi - 1, nt = nil;
␈↓ ↓H␈↓for r in 1 to n do if null ind(r) then
␈↓ ↓H␈↓  (ind(r) := nt := [r];
␈↓ ↓H␈↓   for s in ind(r) do
␈↓ ↓H␈↓      for q in im(s) do if null ind(q) then
␈↓ ↓H␈↓        (ind(q) := ind(r); cdr nt := [q]; nt := cdr nt));
␈↓ ↓H␈↓ind
␈↓ ↓H␈↓        The outermost for-loop looks for towns not yet in equivalence
␈↓ ↓H␈↓classes (LISP initializes untyped arrays to NIL, whence the NULL
␈↓ ↓H␈↓test). When a new town r is found, a length-one equivalence list [r]
␈↓ ↓H␈↓is started for it, and nt is set to the last LISP cell of the list
␈↓ ↓H␈↓(which initially is also the first). Then for each town s on the
␈↓ ↓H␈↓list, towns reachable from s that as yet belong to no list are put at
␈↓ ↓H␈↓the end of this list. (Since "for s in ind(r)" does not make a
␈↓ ↓H␈↓separate copy of the list ind(r) before scanning it, putting more
␈↓ ↓H␈↓towns on the end of the list forces the for-loop to consider those
␈↓ ↓H␈↓towns as well, which is what we want here. Though this is not good
␈↓ ↓H␈↓LISP style, it is how one would use LISP to do what was done in the
␈↓ ↓H␈↓ALGOL program, which is not good style either.) When all towns have
␈↓ ↓H␈↓been put into classes, the array ind is returned. To use the
␈↓ ↓H␈↓subroutine on input array x to find out what towns are accessible from
␈↓ ↓H␈↓town i, say "(orbits x)(i)" which will compute the ind array and then
␈↓ ↓H␈↓apply it to i. This of course is an inefficient use of ORBITS;
␈↓ ↓H␈↓usually one will say "x := orbits y" and later say "x(i)" for each i
␈↓ ↓H␈↓of interest.
␈↓ ↓H␈↓        For those readers wondering how hard I had to look to find an
␈↓ ↓H␈↓example better coded in LISP than ALGOL, I should say that I simply
␈↓ ↓H␈↓selected the most recent short ALGOL contribution to CACM's algorithms



␈↓ ↓H␈↓section that I could find on my bookshelf. I originally had not
␈↓ ↓H␈↓intended to give the second LISP version, but could not resist it once
␈↓ ↓H␈↓I figured out what the algorithm was up to.
␈↓ ↓H␈↓        CGOL is not the only algebraic dialect of LISP available at
␈↓ ↓H␈↓MIT. MACSYMA users also use an MLISP-like algebraic notation - in
␈↓ ↓H␈↓fact MACSYMA's parser is just the CGOL parser modified (by Michael
␈↓ ↓H␈↓Genesereth) to handle typed expressions. Unlike CGOL in plain LISP,
␈↓ ↓H␈↓MACSYMA notation is the default language for MACSYMA users.
␈↓ ↓H␈↓        It must be admitted that any notational change to LISP raises
␈↓ ↓H␈↓the question of what constitutes a programming language. Must one buy
␈↓ ↓H␈↓lexicon, syntax, semantics and object code as a package, or can one
␈↓ ↓H␈↓shop around like a purchaser of a component stereo? The argument of
␈↓ ↓H␈↓this section has assumed that one ␈↓&can␈↓)αβ shop around, but I realize that
␈↓ ↓H␈↓while component stereos may make sense to an electrical engineer, the
␈↓ ↓H␈↓concept of component languages may require some getting used to. I
␈↓ ↓H␈↓feel that this issue drives home the disadvantage of most languages,
␈↓ ↓H␈↓that you cannot use it for its good features without also having to
␈↓ ↓H␈↓accept its bad features. This situation has encouraged an attitude
␈↓ ↓H␈↓among language users that permits arguments of the form, "We can't
␈↓ ↓H␈↓have X because it has a bad feature, namely its syntax." As the
␈↓ ↓H␈↓computer-using community matures, it should grow more accustomed to
␈↓ ↓H␈↓the idea of purchasing language components and assembling them into
␈↓ ↓H␈↓their "ideal" system. As a spin-off from this sort of technology, we
␈↓ ↓H␈↓may hope to see a decrease in the number of languages available, a
␈↓ ↓H␈↓number which from this point of view we can attribute to the
␈↓ ↓H␈↓multiplicative way in which options must increase when you cannot
␈↓ ↓H␈↓order systems component by component. For example, if the community
␈↓ ↓H␈↓demands two kinds of lexicons, two kinds of syntax, two kinds of
␈↓ ↓H␈↓semantics and two kinds of code-generators, the market need supply
␈↓ ↓H␈↓only eight components in place of sixteen systems. Any increase in
␈↓ ↓H␈↓the sizes of the component options results in a rapid widening of this
␈↓ ↓H␈↓gap.
␈↓ ↓H␈↓        In this context the question of whether to choose a widely
␈↓ ↓H␈↓used language must be restated as whether to choose a widely used
␈↓ ↓H␈↓component. This question is perhaps most important for the syntax
␈↓ ↓H␈↓component, which for the user is as at least as visible as any other
␈↓ ↓H␈↓component. Although I suggested above that CGOL or MACSYMA notation
␈↓ ↓H␈↓is a possibility, other notations are equally possible, such as the
␈↓ ↓H␈↓very widely known ALGOL notation. In fact, an ALGOL front-end has
␈↓ ↓H␈↓been built for LISP along the lines of the CGOL front-end (but with
␈↓ ↓H␈↓more attention paid to preserving the semantics of ALGOL than is
␈↓ ↓H␈↓implicit in our translation of the ALGOL example above), and if the
␈↓ ↓H␈↓question of whether the notation was widely known became a serious
␈↓ ↓H␈↓issue, the replacement of CGOL or MACSYMA notation by ALGOL notation
␈↓ ↓H␈↓is straightforward, modulo tortuous implementation when the (rarely
␈↓ ↓H␈↓used in practice) environment-handling capability of ALGOL is given
␈↓ ↓H␈↓full throttle. Our personal feeling is that the CGOL notation is
␈↓ ↓H␈↓already so close to ALGOL notation when it comes to those things one
␈↓ ↓H␈↓regularly wants to say in ALGOL that to insist on one-hundred-percent



␈↓ ↓H␈↓ALGOL notation is gilding the lily for almost all applications.
␈↓ ↓H␈↓        LISP's independence of choice of notation may be of value in
␈↓ ↓H␈↓an educational environment where, although a commitment to a single
␈↓ ↓H␈↓language may have already been made, individual instructors may
␈↓ ↓H␈↓nevertheless have a requirement for a different notation. LISP's
␈↓ ↓H␈↓ability to change notations in midstream without having to change
␈↓ ↓H␈↓languages reduces the overhead associated with maintaining several
␈↓ ↓H␈↓entire languages and their supporting maintenance teams and other
␈↓ ↓H␈↓paraphernalia. For example, if APL were needed on occasion, it would
␈↓ ↓H␈↓not be impossible to embed it in LISP; indeed a very compact
␈↓ ↓H␈↓definition of APL is possible in LISP. However it would seem only
␈↓ ↓H␈↓fair to ask the users of such
␈↓ ↓H␈↓7. LISP is applicative. That is, one can write non-trivial
␈↓ ↓H␈↓programs in LISP using only functional application that in other
␈↓ ↓H␈↓languages would have to be written iteratively or recursively. The
␈↓ ↓H␈↓two LISP functions (strictly, functionals or combinators) that supply
␈↓ ↓H␈↓this power are MAPCAR and APPLY. MAPCAR permits a function to be
␈↓ ↓H␈↓applied to the elements of a list one at a time (coordinate-wise
␈↓ ↓H␈↓operation) while APPLY permits an operation such as PLUS to be applied
␈↓ ↓H␈↓to all the elements of the list (APL's notion of reduction, written
␈↓ ↓H␈↓+/a). APL, like LISP, offers non-applicative features such as
␈↓ ↓H␈↓assignment and goto, but its users are strongly encouraged to rely on
␈↓ ↓H␈↓the applicative part of APL, and (presumably) to ensure that this
␈↓ ↓H␈↓happens APL offers a bare minimum of non-applicative
␈↓ ↓H␈↓control structures. A significant benefit of this style is
␈↓ ↓H␈↓that reasoning about such programs can be done in the same algebraic
␈↓ ↓H␈↓formalism that we have all been raised on since birth, instead of
␈↓ ↓H␈↓having to invent systems of logic especially to cope with the
␈↓ ↓H␈↓non-algebraic control structures of conventional programming
␈↓ ↓H␈↓languages. For example, knowing that + is associative even when
␈↓ ↓H␈↓applied to equal-length vectors as opposed to scalars, we can
␈↓ ↓H␈↓immediately see that (u+v)+w computes the same vector as u+(v+w),
␈↓ ↓H␈↓whereas we may have to argue more indirectly about the effect of the
␈↓ ↓H␈↓corresponding two programs in a non-applicative (in this case
␈↓ ↓H␈↓non-vector-manipulating) language. Vector spaces have been well
␈↓ ↓H␈↓studied and their properties carry over readily to reasoning about APL
␈↓ ↓H␈↓programs.
␈↓ ↓H␈↓        Let us give some examples where LISP can be used as an
␈↓ ↓H␈↓applicative language. The CGOL notation a[[b]] for (MAPCAR 'a b)
␈↓ ↓H␈↓helps to emphasize the functional nature of MAPCAR, inasmuch as
␈↓ ↓H␈↓a[[[b0, b1, b2]]] (where [b0, b1, b2] is the list being operated on)
␈↓ ↓H␈↓means simply the list [a(b0), a(b1), a(b2)] . (The reason for two
␈↓ ↓H␈↓brackets is that two separate operations are really invoked by a[[b]],
␈↓ ↓H␈↓which is equivalent to a[x] where x is [b] (the list whose only
␈↓ ↓H␈↓element is b). Thus when u and v are added coordinatewise using
␈↓ ↓H␈↓plus[[u,v]], in fact the operation is plus[x] where x is the
␈↓ ↓H␈↓two-element list [u,v].) Likewise the notation a{b} for (APPLY 'a b)
␈↓ ↓H␈↓emphasizes that a is just being applied to the list of arguments b.
␈↓ ↓H␈↓Thus given a list b of numbers, plus{b} yields its sum, corresponding



␈↓ ↓H␈↓to +/b in APL. Given two lists a and b, plus[[a,b]] yields the list
␈↓ ↓H␈↓which is the coordinate-wise sum of the two lists, corresponding to
␈↓ ↓H␈↓APL's (syntactically more succinct but no more or less applicative)
␈↓ ↓H␈↓a+b. Thus to compute the inner product of two vectors (represented as
␈↓ ↓H␈↓lists though the semantics of LISP does not forbid lists being
␈↓ ↓H␈↓represented internally as vectors when appropriate) it suffices to
␈↓ ↓H␈↓write plus{times[[a,b]]}, corresponding to APL's +/a*b. One way to
␈↓ ↓H␈↓write a one-line matrix multiplication routine in LISP (yes, APL has
␈↓ ↓H␈↓no monopoly on one-liners) would be
␈↓ ↓H␈↓  for i in x collect for j in list[y] collect plus{times[[x,y]]} .
␈↓ ↓H␈↓        (Here list[y] transposes the list of lists y, representing a
␈↓ ↓H␈↓matrix stored as a list of rows, for reasons about as obscure as those
␈↓ ↓H␈↓that account for a variety of APL techniques such as conditional
␈↓ ↓H␈↓goto. The reader who followed our explanation earlier of what a[b]
␈↓ ↓H␈↓did will realize that list[y] is equivalent to list[[y0,y1,...]] where
␈↓ ↓H␈↓y = [y0,y1,...].) In this example I have deliberately avoided the
␈↓ ↓H␈↓equivalent more succinct but less transparent syntactic variant of the
␈↓ ↓H␈↓above,
␈↓ ↓H␈↓    (\i;(\j;plus{times[[i,j]]})[[list[y]]])[[x]]
␈↓ ↓H␈↓This is an example of where LISP's versatility permits the user to
␈↓ ↓H␈↓avoid the APL trap of being forced to write code applicatively even
␈↓ ↓H␈↓when it might be better understood by writing it dynamically using a
␈↓ ↓H␈↓"for" loop. (Strictly speaking, the APL user does have the option of
␈↓ ↓H␈↓a dynamic solution, as goto exists in the language; however there are
␈↓ ↓H␈↓dynamic solutions and dynamic solutions, and code written with goto's
␈↓ ↓H␈↓rarely constitutes an improvement over other arcane solutions to
␈↓ ↓H␈↓programming tasks.)
␈↓ ↓H␈↓        In some respects LISP's applicative ability is superior to
␈↓ ↓H␈↓APL's. APL lacks a specific operator that permits coordinate-wise
␈↓ ↓H␈↓application of a scalar operator, but rather relies on the fact that a
␈↓ ↓H␈↓scalar operation is being applied to a vector to deduce that
␈↓ ↓H␈↓coordinate-wise operation is called for. When a user has defined an
␈↓ ↓H␈↓operation that applies equally well to scalars and vectors, he cannot
␈↓ ↓H␈↓specify to APL whether or not he wants to apply his operation to the
␈↓ ↓H␈↓list as an entity or coordinatewise to its individual components. In
␈↓ ↓H␈↓LISP one distinguishes these cases explicitly as a(b) versus a[[b]].
␈↓ ↓H␈↓8. LISP is widely used in academia. In a large portion of the
␈↓ ↓H␈↓academic computing community LISP is either a first or a second
␈↓ ↓H␈↓language. I received last week a letter from Gene Freuder, a recent
␈↓ ↓H␈↓MIT graduate now teaching at Indiana, where he is their AI
␈↓ ↓H␈↓representative. He was happy to report that in his department
␈↓ ↓H␈↓"everyone speaks LISP as a mother tongue." While one might not be
␈↓ ↓H␈↓surprised to hear this about a department with a heavy AI bias, it is
␈↓ ↓H␈↓a tribute to LISP's ubiquity that it should be so honored in a
␈↓ ↓H␈↓department noted primarily for its work on programming languages and
␈↓ ↓H␈↓multiple-valued logic.
␈↓ ↓H␈↓9. LISP is used by half the MIT Computer Science faculty. Thus
␈↓ ↓H␈↓choosing LISP as the main departmental language, if one language is to
␈↓ ↓H␈↓be chosen ueber alles, would seem to involve the least upheaval.



␈↓ ↓H␈↓Further, LISP as a high quality language attracts high quality
␈↓ ↓H␈↓maintenance personnel. LISP has been maintained here not only by Jon
␈↓ ↓H␈↓L. White, a very experienced LISP systems programmer, but by some of
␈↓ ↓H␈↓the sharpest graduate students in the world. Guy L. Steele, winner of
␈↓ ↓H␈↓the 1975 George Forsythe student paper competition [9], the main
␈↓ ↓H␈↓student-paper competition in the computer-science world, has been a
␈↓ ↓H␈↓shining example of such help for several years dating back to his
␈↓ ↓H␈↓undergraduate days. The situation seems simply to be that the best
␈↓ ↓H␈↓languages attract the best students. Unless MIT suddenly experiences
␈↓ ↓H␈↓a dearth of good students, a fate few of us want even to contemplate,
␈↓ ↓H␈↓this high quality maintenance should continue at or near its present
␈↓ ↓H␈↓enviably high level.
␈↓ ↓H␈↓10. No other language enjoys all the above advantages of LISP.
␈↓ ↓H␈↓This remains true even if advantages 2 and 4 are omitted. Let us
␈↓ ↓H␈↓argue this point on a language-by-language basis, choosing (at the
␈↓ ↓H␈↓risk of offending all whose languages have been omitted) FORTRAN,
␈↓ ↓H␈↓COBOL, ALGOL, PL/I, APL, ALGOL 68 and PASCAL. In the following we
␈↓ ↓H␈↓omit reference to items 2, 4, and 9; the first two are easy to satisfy
␈↓ ↓H␈↓while the last is obviously impossible.
␈↓ ↓H␈↓FORTRAN: This fails on items 1, 5, 6 and 7. FORTRAN's storage
␈↓ ↓H␈↓allocation facilities and control primitives are too rudimentary to
␈↓ ↓H␈↓make FORTRAN useful outside the domain of numerical arrays, for which
␈↓ ↓H␈↓it was designed. By bending over backwards one can do anything in
␈↓ ↓H␈↓FORTRAN, as in any universal language (in Turing's sense); for example
␈↓ ↓H␈↓Joseph Weizenbaum implemented SLIP, a list processing language, in
␈↓ ↓H␈↓FORTRAN, and it is the language used for symbol manipulation at Bell
␈↓ ↓H␈↓Laboratories. However, one is sufficiently hemmed in by petty
␈↓ ↓H␈↓restrictions and inadequate data and control structures that no very
␈↓ ↓H␈↓strong case can be made for it.
␈↓ ↓H␈↓COBOL. COBOL has something to offer academia that FORTRAN lacks, and
␈↓ ↓H␈↓that is a "data division" (to use COBOL terminology) that permits the
␈↓ ↓H␈↓user to define a rich variety of data types. This can lead to
␈↓ ↓H␈↓considerable simplification of the "program division," since the COBOL
␈↓ ↓H␈↓compiler can automatically make many decisions about where to put
␈↓ ↓H␈↓things and how to represent them. Unfortunately COBOL's data types
␈↓ ↓H␈↓are rich in about the same sense that an Eskimo finds a richness of
␈↓ ↓H␈↓snow varieties in the Arctic; this richness goes unappreciated in
␈↓ ↓H␈↓other climates, and COBOL's concern with business data processing
␈↓ ↓H␈↓makes it too narrow for use in other environments. We can rule out
␈↓ ↓H␈↓COBOL on the same grounds as FORTRAN, together with item 8.
␈↓ ↓H␈↓ALGOL. A discussion earlier (item 6) of LISP's ability to disguise
␈↓ ↓H␈↓itself as an ALGOL-like language revealed a serious lack of
␈↓ ↓H␈↓versatility in ALGOL. Actually, ALGOL's control structures are
␈↓ ↓H␈↓remarkably powerful; one can do truly astonishing things with ALGOL's
␈↓ ↓H␈↓goto statement, such as jumping out of a procedure body that has
␈↓ ↓H␈↓called itself recursively to a great depth, resulting in exiting from
␈↓ ↓H␈↓all those levels of recursion in response to one ␈↓&goto␈↓)αβ. Also ALGOL
␈↓ ↓H␈↓offers call by name, which permits such useful constructs as Jensen's
␈↓ ↓H␈↓device for implementing a summation operator. Unfortunately these



␈↓ ↓H␈↓strengths of ALGOL do not make up for its weakness in the versatility
␈↓ ↓H␈↓of its data types. ALGOL fails on items 1, 3 (to a small but not
␈↓ ↓H␈↓terribly important extent), 5, 6, and 7.
␈↓ ↓H␈↓PL/I. PL/I is nothing if not versatile. At least that is what IBM
␈↓ ↓H␈↓had in mind when they designed it. However, to be versatile without
␈↓ ↓H␈↓being modular is to be a super-market, where sometimes you spend more
␈↓ ↓H␈↓time looking for the aisle you need than all the other operations
␈↓ ↓H␈↓combined. PL/I fails on items 5, 6 and 7, as well as 1 in my opinion.
␈↓ ↓H␈↓APL. APL passes strongly on item 7 (applicative), though not
␈↓ ↓H␈↓without a black mark for being unable to distinguish a(b) from a[[b]]
␈↓ ↓H␈↓(using CGOL notation). For what it attempts to be, namely a
␈↓ ↓H␈↓vector-manipulating language, it also does well on item 1. Though we
␈↓ ↓H␈↓promised to omit reference to item 4 (interactive), this is a very
␈↓ ↓H␈↓strong feature of APL, and supplied me with my one reason to use APL
␈↓ ↓H␈↓considerably during a summer visit to IBM. Unfortunately, little of
␈↓ ↓H␈↓my work happened to fit the vector mold very well, despite the fact
␈↓ ↓H␈↓that most of it was heavily numerical, and I found myself from time to
␈↓ ↓H␈↓time using the embryonic 360 LISP system maintained by Fred Blair at
␈↓ ↓H␈↓IBM, on the ground that the additional time I had to spend running
␈↓ ↓H␈↓back and forth between the CP/CMS editor and LISP was made up for by
␈↓ ↓H␈↓the considerably decreased programming time in LISP. Thus I would
␈↓ ↓H␈↓fail APL on item 1, though not as seriously as the above languages.
␈↓ ↓H␈↓What really makes APL totally unacceptable is the insistence on a
␈↓ ↓H␈↓character set so out of touch with the ASCII standard that the
␈↓ ↓H␈↓department would be locked into an unacceptably inflexible (not to say
␈↓ ↓H␈↓expensive) situation if it were to generally adopt APL. APL also
␈↓ ↓H␈↓fails on 5 and 6.
␈↓ ↓H␈↓ALGOL 68. This language is full of nice ideas. It has been
␈↓ ↓H␈↓carefully thought about by people with a concern for elegance and
␈↓ ↓H␈↓mathematical precision. Unfortunately the former has been sacrificed
␈↓ ↓H␈↓to the latter, and to learn ALGOL 68 requires considerable patience
␈↓ ↓H␈↓while one discovers the correspondence between one's programming
␈↓ ↓H␈↓intuition and the picturesque vocabulary of an ALGOL 68 programming
␈↓ ↓H␈↓guide (not to be confused with the language's formal definition, which
␈↓ ↓H␈↓is written in a relatively inaccessible meta-language). ALGOL 68
␈↓ ↓H␈↓fails on items 6, 7 and 8.
␈↓ ↓H␈↓PASCAL. Nicklaus Wirth sensibly designed PASCAL to be simple in
␈↓ ↓H␈↓concept, easy to implement, efficient, yet versatile in its data
␈↓ ↓H␈↓types. Moreover, he saw to it that a good implementation on a machine
␈↓ ↓H␈↓commonly found in universities (a large CDC machine) was made
␈↓ ↓H␈↓available. As a result, PASCAL has attracted the attention of many
␈↓ ↓H␈↓computer science departments as being an ideal pedagogical language.
␈↓ ↓H␈↓PASCAL's greatest drawback is the extent to which Wirth had to
␈↓ ↓H␈↓compromise to achieve ease of implementation. As a result, PASCAL
␈↓ ↓H␈↓(like every other language above) lacks the first-class-citizen
␈↓ ↓H␈↓property that makes LISP so pleasant to use yet simple to implement in
␈↓ ↓H␈↓the event that you are willing to forego efficiency on some of the
␈↓ ↓H␈↓data types. I believe that this concession to efficiency, while it
␈↓ ↓H␈↓has many merits, detracts considerably from PASCAL's otherwise



␈↓ ↓H␈↓excellent versatility. Nevertheless, PASCAL remains among the more
␈↓ ↓H␈↓attractive possibilities.
␈↓ ↓H␈↓B. DRAWBACKS OF LISP.
␈↓ ↓H␈↓        Most of the complaints of this section are
␈↓ ↓H␈↓implementation-specific and do not inhere in the LISP language itself.
␈↓ ↓H␈↓The one major exception to this is LISP's typelessness. It is
␈↓ ↓H␈↓unlikely that future implementations of LISP will clear up this issue
␈↓ ↓H␈↓without introducing substantial incompatibilities with existing LISP
␈↓ ↓H␈↓software. Moreover, many feel that typelessness is more virtue than
␈↓ ↓H␈↓vice. In contrast, The various complaints about the implementation
␈↓ ↓H␈↓cannot be taken seriously from a long-term stand-point. Other
␈↓ ↓H␈↓implementations of LISP are presently in an experimental stage, one in
␈↓ ↓H␈↓hardware (Richard Greenblatt's LISP machine) and one using the lexical
␈↓ ↓H␈↓scoping of the lambda calculus (Guy Steele and Gerald Sussman). Thus
␈↓ ↓H␈↓implementation-specific properties of LISP are at present in a state
␈↓ ↓H␈↓of flux, and taking them into account in deciding that LISP was
␈↓ ↓H␈↓inadequate would be a case of throwing out the baby with the
␈↓ ↓H␈↓bathwater. Let us now begin with my one implementation-independent
␈↓ ↓H␈↓complaint.
␈↓ ↓H␈↓        LISP does not in any systematic way permit the user to specify
␈↓ ↓H␈↓the types of his data and variables. In fact some types are
␈↓ ↓H␈↓implemented directly as other types without LISP being able to tell
␈↓ ↓H␈↓which type is intended. For example, NIL serves double duty as the
␈↓ ↓H␈↓boolean FALSE and the empty list, as well as being recognized by LISP
␈↓ ↓H␈↓as an atom (though not one that can be used as a variable). And bit
␈↓ ↓H␈↓vectors are just single-precision integers; indeed only the presence
␈↓ ↓H␈↓of bit-manipulating operations permits LISP to claim that it has the
␈↓ ↓H␈↓type bit vector. Though this typelessness of LISP has an advantage in
␈↓ ↓H␈↓permitting the user to save programming time by not having to declare
␈↓ ↓H␈↓types, there remains the fact that many bugs are detectable because
␈↓ ↓H␈↓they violate type constraints. These violations will be caught by the
␈↓ ↓H␈↓interpreter (if at all) only when the offending portion of the code is
␈↓ ↓H␈↓actually run; for this reason some LISP users compile their newly
␈↓ ↓H␈↓written code before or even instead of debugging it interpretively as
␈↓ ↓H␈↓a first debugging step on the ground that at least the compiler does a
␈↓ ↓H␈↓fair to moderate job of detecting type violations. This philosophy of
␈↓ ↓H␈↓tight control over types is at the heart of the design philosophy of
␈↓ ↓H␈↓Barbara Liskov's CLU language at MIT along with similar research
␈↓ ↓H␈↓languages at other campuses such as Carnegie-Mellon's ALPHARD
␈↓ ↓H␈↓language.
␈↓ ↓H␈↓        Another source of troubles with LISP is the classic FUNARG
␈↓ ↓H␈↓problem, so named by Joel Moses [4] in an early discussion of the
␈↓ ↓H␈↓problem. Although a completely correct handling of this problem is
␈↓ ↓H␈↓not at the top of all users' lists of demands, it is for some; also,
␈↓ ↓H␈↓the formal description of LISP is simplified if one assumes that the
␈↓ ↓H␈↓problem, which involves being able to pass around program-environment
␈↓ ↓H␈↓pairs just like any other data, is properly taken care of. As things
␈↓ ↓H␈↓stand at present, the partial solution implemented in MACLISP is
␈↓ ↓H␈↓better described operationally, leading to a more clumsy description



␈↓ ↓H␈↓of LISP than is possible otherwise. Several plausible solutions
␈↓ ↓H␈↓(by Richard Greenblatt, Henry Baker, Guy Steele and Gerald Sussman) are
␈↓ ↓H␈↓in the air, and one may soon find its way into MACLISP.
␈↓ ↓H␈↓        A much less serious complaint is that the user may not specify
␈↓ ↓H␈↓a lower bound for any array dimension other than 0. To an extent this
␈↓ ↓H␈↓objection can be overcome using the notational flexibility discussed
␈↓ ↓H␈↓in section 6 by permitting a(i) to denote (A (PLUS I 7)) or whatever.
␈↓ ↓H␈↓Another complaint is that with the bit-vector data type, LISP itself
␈↓ ↓H␈↓only offers 36-bit bit vectors. However, LIBLSP (the public LISP
␈↓ ↓H␈↓software library on the ITS machines) offers a package written by
␈↓ ↓H␈↓Henry Baker that confers efficient unlimited-length bit-vector
␈↓ ↓H␈↓processing capability on LISP. This package really ought to be
␈↓ ↓H␈↓available directly to LISP users. In my LINGOL natural language
␈↓ ↓H␈↓system, which does a considerable amount of set-oriented processing
␈↓ ↓H␈↓involving set intersection and union, bit vectors have supplied a very
␈↓ ↓H␈↓efficient implementation of sets.
␈↓ ↓H␈↓        A continual source of petty irritation for me is the compiler,
␈↓ ↓H␈↓which overlooks many simple optimizations. However, my pique
␈↓ ↓H␈↓notwithstanding, the compiler is probably the best LISP compiler
␈↓ ↓H␈↓available anywhere as it does a remarkably good job of optimization
␈↓ ↓H␈↓considering LISP's versatility. No matter what language the
␈↓ ↓H␈↓department settles on, if it is as powerful as LISP, people will be
␈↓ ↓H␈↓complaining about overlooked "obvious" optimizations for quite a
␈↓ ↓H␈↓while, possibly for ever.
␈↓ ↓H␈↓        One can come up with a variety of minor complaints of this
␈↓ ↓H␈↓ilk, but beyond the first two major complaints about LISP's
␈↓ ↓H␈↓typelessness (regarded by many others as a virtue) and lack of
␈↓ ↓H␈↓environment-manipulating capability, I personally am pretty satisfied
␈↓ ↓H␈↓with the language.
␈↓ ↓H␈↓C. DEPARTMENTAL REQUIREMENTS.
␈↓ ↓H␈↓        Though the department has asked for a good educational
␈↓ ↓H␈↓language, there is no harm (if we are considering LISP) in asking that
␈↓ ↓H␈↓the research needs of the department also be considered. Here are a
␈↓ ↓H␈↓number of headings (suggested to me by Ronald Rivest) under which one
␈↓ ↓H␈↓may ask about the utility of LISP.
␈↓ ↓H␈↓1. Desktop calculators. As pointed out before, one need merely type
␈↓ ↓H␈↓1+2*3 followed by a termination character to get the answer 7.
␈↓ ↓H␈↓Although my secretary cannot program she has used LISP regularly for
␈↓ ↓H␈↓two years for precisely this application, even though the bulk of her
␈↓ ↓H␈↓arithmetic is just adding up numbers. In fact almost any expression
␈↓ ↓H␈↓that can be typed on an SR-51, say, can be typed almost verbatim to
␈↓ ↓H␈↓LISP. Moreover, the comparatively unlimited storage of LISP is
␈↓ ↓H␈↓available for storing intermediate results. Thus a LISP terminal
␈↓ ↓H␈↓consisting of a calculator-sized keyboard and a 15-digit display would
␈↓ ↓H␈↓already provide enormous power. Going to a 30-character alphanumeric
␈↓ ↓H␈↓display would increase the utility of such a terminal considerably.
␈↓ ↓H␈↓Such terminals could be so cheap that each office in the building
␈↓ ↓H␈↓could have two or more if necessary. With reasonable system design,
␈↓ ↓H␈↓the formalities of logging such terminals on and off could be



␈↓ ↓H␈↓dispensed with. Thus LISP would be available as a powerful
␈↓ ↓H␈↓replacement for programmable calculators, yet lacking none of their
␈↓ ↓H␈↓convenience. The possibility exists of making such terminals
␈↓ ↓H␈↓completely portable, at least within the building, relying on a radio
␈↓ ↓H␈↓link for contact with the department's system.
␈↓ ↓H␈↓2. Number-crunching. We have already referred to Bers' Plasma
␈↓ ↓H␈↓Dynamics group, in the section on efficiency. This supplies an
␈↓ ↓H␈↓example of where LISP is already in use within the department for
␈↓ ↓H␈↓"number-crunching" on a large scale.
␈↓ ↓H␈↓3. Classroom language. Not surprisingly, LISP is the classroom
␈↓ ↓H␈↓language for Patrick Winston's AI course. Perhaps more surprisingly
␈↓ ↓H␈↓is that it is also the language for my undergraduate algorithms
␈↓ ↓H␈↓course, which teaches the sort of material one finds in Donald Knuth's
␈↓ ↓H␈↓volumes on algorithms. We deal with graph and matrix algorithms, bit
␈↓ ↓H␈↓vector algorithms, integer and real arithmetic, storage management,
␈↓ ↓H␈↓information organization and retrieval, and sorting. The language
␈↓ ↓H␈↓(which I call "The 6.046 programming language" so that any opponents
␈↓ ↓H␈↓of LISP in the class won't take offence - they don't recognize LISP in
␈↓ ↓H␈↓its algebraic dialect) is spelled out in a class handout and students
␈↓ ↓H␈↓are required to stick to it. This gives the students a
␈↓ ↓H␈↓simple-to-learn yet versatile and well-defined language that simplifies
␈↓ ↓H␈↓our grading. The versatility of LISP simplifies many of the
␈↓ ↓H␈↓algorithms I teach, and at the same time makes it possible for us to
␈↓ ↓H␈↓run a student's algorithm on the computer if neither the T.A.'s nor I
␈↓ ↓H␈↓can understand what it is supposed to be doing, a feature we
␈↓ ↓H␈↓occasionally take advantage of. It is regrettable that we cannot
␈↓ ↓H␈↓offer unlimited access to LISP for the students, a fact we have to
␈↓ ↓H␈↓keep perpetually in mind when setting and grading problems requiring
␈↓ ↓H␈↓some programming.
␈↓ ↓H␈↓4. Publication Language. This is one area where the case for LISP is
␈↓ ↓H␈↓not strong. Although LISP's standard notation is popular with many
␈↓ ↓H␈↓LISP users, it does take sufficient getting used to that it is not an
␈↓ ↓H␈↓appropriate publication language except in AI circles, since outside
␈↓ ↓H␈↓of AI the world is very algebraically oriented. The fact that an
␈↓ ↓H␈↓algebraic dialect for LISP only helps if that dialect is well known,
␈↓ ↓H␈↓or at least understandable without lots of explanation, which is not
␈↓ ↓H␈↓at present the case for any of the MLISP, CGOL or MACSYMA dialects.
␈↓ ↓H␈↓One solution is to translate the algebraic dialect into a well-known
␈↓ ↓H␈↓language; this may only be possible if some restraint is used in
␈↓ ↓H␈↓taking advantage of LISP's versatility. Another possibility is to go
␈↓ ↓H␈↓ahead and use an algebraic dialect of full-blown LISP on the
␈↓ ↓H␈↓chauvinistically evangelical ground that the rest of the world ought
␈↓ ↓H␈↓to learn such a lovely language, especially when they aren't being
␈↓ ↓H␈↓asked to suffer the fully parenthesized notation. This issue should
␈↓ ↓H␈↓be brought up in any defense of PASCAL, where it is more reasonable at
␈↓ ↓H␈↓present to assume that the reader can follow PASCAL code.
␈↓ ↓H␈↓        In summary, I would say very simply that LISP would make an
␈↓ ↓H␈↓excellent departmental language. All things considered, it has little
␈↓ ↓H␈↓serious competition from any language except PASCAL, and even that



␈↓ ↓H␈↓competition is minimal. At this point it is appropriate to include
␈↓ ↓H␈↓the ␈↓&ad␈↓)αβ ␈↓&hominem␈↓)αβ argument that LISP, an MIT product, has had a
␈↓ ↓H␈↓considerable impact on the academic computing community over the past
␈↓ ↓H␈↓decade and a half, and along with magnetic core storage, CTSS, MULTICS
␈↓ ↓H␈↓and MACSYMA has been responsible for making MIT close to the world's
␈↓ ↓H␈↓most influential source of Computer Science ideas.
␈↓ ↓H␈↓Bibliography.
␈↓ ↓H␈↓[1] Fateman, Richard J. "Reply to an Editorial." SIGSAM Bulletin
␈↓ ↓H␈↓25, 9-11. (March 1973).
␈↓ ↓H␈↓[2] Hewitt, C. E., P. Bishop, and R. Steiger. "A Universal
␈↓ ↓H␈↓Modular ACTOR Formalism for Artificial Intelligence," Proc. IJCAI
␈↓ ↓H␈↓3, p. 235. 1973.
␈↓ ↓H␈↓[3] McKay, John and E. Regener. "Transitivity Sets." Algorithm
␈↓ ↓H␈↓482, CACM ␈↓&17␈↓)αβ, 8, 470. (August 1974).
␈↓ ↓H␈↓[4] Moses, Joel. "The Function of FUNCTION in LISP." AI Memo 199,
␈↓ ↓H␈↓MIT AI Lab (Cambridge, June 1970).
␈↓ ↓H␈↓[5] Popplestone, R. J. "The Design Philosophy of POP-2." Machine
␈↓ ↓H␈↓Intelligence 3 (ed. D. Michie), 393-402, Edinburgh U. Press, 1968.
␈↓ ↓H␈↓[6] Pratt, V. R. "Top Down Operator Precedence." Proc. ACM
␈↓ ↓H␈↓SIGACT/SIGPLAN Conf. on Principles of Programming Languages (POPL 1),
␈↓ ↓H␈↓Boston. (October 1973).
␈↓ ↓H␈↓[7] --------. "A Linguistics Oriented Programming Language."
␈↓ ↓H␈↓Proc. 3rd International Joint Conference on AI, Stanford, 1973.
␈↓ ↓H␈↓[8] --------. "CGOL - an Alternative External Representation
␈↓ ↓H␈↓For LISP Users." MIT AI Lab Working Paper 89. 1976.
␈↓ ↓H␈↓[9] Steele, Guy Lewis Jr. "Multiprocessing Compactifying Garbage
␈↓ ↓H␈↓Collection." Comm. ACM 18, 9, 495-508. (September 1975).